package backdate;

import java.util.LinkedList;
import java.util.Queue;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/9h6vo2/
public class LCR_130衣橱整理 {
    //dfs
    class Solution {
        int m, n, cnt;
        boolean[][] visited;
        public int wardrobeFinishing(int m, int n, int cnt) {
            this.m = m; this.n = n; this.cnt = cnt;
            this.visited = new boolean[m][n];
            return dfs(0, 0, 0, 0);
        }
        public int dfs(int i, int j, int si, int sj) {
            if(i>=m || j>=n || cnt < si + sj || visited[i][j]) return 0;
            visited[i][j] = true;
            return 1 + dfs(i+1,j,(i+1) % 10 != 0 ? si+1 : si-8,sj) +
                    dfs(i,j+1,si,(j+1) % 10 != 0 ? sj+1 : sj-8);
        }
    }
    //bfs
    class Solution2 {
        public int wardrobeFinishing(int m, int n, int cnt) {
            boolean[][] visited = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[] {0,0,0,0});
            int res = 0;
            while (!queue.isEmpty()){
                int[] x = queue.poll();
                int i = x[0], j = x[1], si = x[2], sj = x[3];
                if(i>=m || j>=n || cnt < si + sj || visited[i][j]) continue;
                visited[i][j] = true;
                res++;


                queue.add(new int[] {i+1,j,(i+1) % 10 != 0 ? si+1 : si-8,sj});
                queue.add(new int[] {i,j+1,si,(j+1) % 10 != 0 ? sj+1 : sj-8});
            }
            return res;
        }
    }
}
